index.md (2268B)
1 +++ 2 title = 'Multiplication of signed integers' 3 +++ 4 # Multiplication of signed integers 5 Meaning 2’s complement signed ints. 6 There’s the shorthand and then there’s the algorithm. 7 8 ## Shorthand (same as decimal multiplication) 9 10  11 12 ## Booth’s algorithm: 13 Involves recoding the multiplier (Y in “X times Y”) based on this table, going bitwise left to right. 14 15 If the last bit is a 1, there’s an implied 0 behind it. 16 17  18 19 Then you do a table, going bitwise right to left on recoded multiplier. If it’s zero, you shift. If it’s -1, you add -A and shift. If it’s +1, you add A and shift. 20 21 For example, if given 001111 × 001111: 22 23 ``` 24 A = 001111 25 B = 001111 26 -A = 110001 27 ``` 28 29 Recoded multiplier (B): `0 +1 0 0 0 -1` 30 31 | Product | Step description | Multiplier bit | 32 | --- | --- | --- | 33 | 000000 | Initialise | - | 34 | 110001 | Add -A | -1 | 35 | 1110001 | Shift | | 36 | 11110001 | Shift only | 0 | 37 | 111110001 | Shift only | 0 | 38 | 1111110001 | Shift only | 0 | 39 | 0011100001 | Add +A | +1 | 40 | 00011100001 | Shift | | 41 | 000011100001 | Shift only | 0 | 42 43 So the final result is `000011100001` (twice as many bits as the terms). 44 45 ## Speeding up the process 46 Bit-pair recoding of multipliers using Booth recoding: 47 48  49 50 For example, for the multiplier `111010`: 51 52  53 54 To multiply by -1, make 2’s complement. To multiply by -2, add 2’s complement. So now the process is: 55 56  57 58 You could also do carry-save addition, which is a crazy-ass circuit where the carries are introduced into the next row at the correct weighted positions. 59 60 Then there’s 3-2 reducer addition: carry-save add summands in groups of 3 to get S and C vectors, group S and C vectors in 3s and carry-save add, etc. until there are only two vectors left. Those are added by carry-save. 61 62 Also, 4-2 reducer addition: 63 64 - s, c, and cout represent arithmetic sum of five inputs 65 - output s is the sum variable (XOR of five inputs) 66 - cout is independent of cin, only function of four inputs. 67 - steps: 68 69 1. cout is 1 when two or more inputs are 1 70 2. other carry (c) is determined to satisfy arithmetic condition